class Solution(object):
    def shortestDistance(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m = len(grid)
        n = len(grid[0])
        search_set = set()
        no_pass_set = set()
        search_grid = [[0 for _ in range(n)] for _ in range(m)]
        pass_set = set()
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    search_set.add((i, j))
                    no_pass_set.add((i, j))
                    search_grid[i][j] = -1
                else:
                    if grid[i][j] == 2:
                        no_pass_set.add((i, j))
                        search_grid[i][j] = -1
                    else:
                        pass_set.add((i, j))
        total_count = len(pass_set)
        for item in search_set:
            already_set = set()
            dist = 1
            now_layer = set()
            count = 0
            for ux, uy in [(item[0] - 1, item[1]), (item[0] + 1, item[1]), (item[0], item[1] - 1),
                           (item[0], item[1] + 1)]:
                if 0 <= ux < m and 0 <= uy < n:
                    if (ux, uy) not in already_set and (ux, uy) not in no_pass_set:
                        already_set.add((ux, uy))
                        now_layer.add((ux, uy))
                        search_grid[ux][uy] += dist
                        count += 1
            dist += 1
            while now_layer:
                next_layer = set()
                for t in now_layer:
                    for ux, uy in [(t[0] - 1, t[1]), (t[0] + 1, t[1]), (t[0], t[1] - 1),
                                   (t[0], t[1] + 1)]:
                        if 0 <= ux < m and 0 <= uy < n:
                            if (ux, uy) not in already_set and (ux, uy) not in no_pass_set:
                                already_set.add((ux, uy))
                                next_layer.add((ux, uy))
                                search_grid[ux][uy] += dist
                                count += 1
                now_layer = next_layer
                dist += 1
            if count < total_count:
                total_count = count
                not_allow_point = pass_set - already_set
                no_pass_set.update(not_allow_point)
                pass_set = already_set
        if not pass_set:
            return -1
        min_dist = float('inf')
        for i in range(m):
            for j in range(n):
                if (i, j) not in no_pass_set:
                    min_dist = min(min_dist, search_grid[i][j])
        return min_dist


data = Solution()
grid = [[1, 0, 2, 0, 1], [0, 0, 0, 0, 0], [0, 0, 1, 0, 0]]
print(data.shortestDistance(grid))
grid = [[1, 0]]
print(data.shortestDistance(grid))
grid = [[1]]
print(data.shortestDistance(grid))
grid = [[1, 1, 1, 1, 1, 0], [0, 0, 0, 0, 0, 1], [0, 1, 1, 0, 0, 1], [1, 0, 0, 1, 0, 1], [1, 0, 1, 0, 0, 1],
        [1, 0, 0, 0, 0, 1], [0, 1, 1, 1, 1, 0]]
print(data.shortestDistance(grid))
grid = [[1, 2, 0]]
print(data.shortestDistance(grid))